Organizations are presently using cloud-based storage systems to store large volumes of data. These cloud-based storage systems are typically operated by hosting companies that maintain a sizable storage infrastructure, often comprising thousands of servers that are sited in geographically distributed data centers. Customers typically buy or lease storage capacity from these hosting companies. In turn, the hosting companies provision storage resources according to the customers' requirements and enable the customers to access these storage resources.
To provide fault tolerance, data items are often replicated across multiple storage locations. In this way, if a storage location fails or becomes inaccessible, the data items on the failed storage location can be accessed from other storage locations. However, this replication can complicate the process of deleting a data item, because to complete the delete operation, the replicated copies of the data item need to be deleted from multiple storage locations. However, asynchronously propagating a delete operation to multiple storage locations can cause race conditions between the delete operation and associated put operations directed to the same data item. Such race conditions can cause inconsistent execution sequences among the different storage locations that can lead to inconsistent copies of data items at the different storage locations.
Hence, what is needed is a technique for performing distributed delete operations in a replicated data storage system without the above-described problems.